/*www.benjamin-dillenburger.com*/

package pGeom2D;

import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
import java.util.Vector;

import processing.core.*;

public class PConvexHull {

	public Vector<PVector> pts;
	public Vector<PVector> hull;

	public PConvexHull(Vector<? extends PVector> p) {

		hull = computeHull(p);
	}

	public Vector<PVector> getConvexHull() {
		return hull;
	}

	private Vector<PVector> computeHull(Vector<? extends PVector> p) {
		pts = new Vector<PVector>(p);
		// pts.addAll(p);
		if (pts.size() < 3)
			return pts;
		return grahamScan();

	}

	/*
	 * public Vector<PVector> computeHullPolygon(Vector<PVector> p) { pts = new
	 * Vector<PVector>(); pts.addAll(p); if (pts.size() < 3) return pts; return
	 * computeHull(p);
	 * 
	 * }
	 */

	private Vector<PVector> computeHullOfSorted2(Vector<PVector> pts) {
		Vector<PVector> hull = new Vector<PVector>();
		PVector p0 = pts.firstElement();
		hull.add(p0);

		PVector p1 = pts.get(1);
		hull.add(p1);

		PVector p2 = pts.get(2);
		hull.add(p2);

		for (int i = 3; i < pts.size(); i++) {
			p0 = p1;
			p1 = p2;
			p2 = pts.get(i);
			hull.add(p2);

			while (PVecMath2D.relativeCCW(p0, p2, p1) == PVecMath2D.CWRIGHT) {
				hull.remove(hull.size() - 2);
				p1 = p0;
				p0 = hull.get(hull.size() - 3);
			}
		}
		return hull;
	}

	private Vector<PVector> computeHullOfSorted(Vector<PVector> pts) {
		// Vector<PVector> hull = new Vector<PVector>();
		Stack<PVector> hull = new Stack<PVector>();
		PVector p0 = pts.firstElement();
		hull.add(p0);
		PVector p1 = pts.get(1);
		hull.add(p1);
		int n = pts.size();
		int i = 2;
		while (i < n) {
			p0 = hull.peek();
			p1 = hull.get(hull.size() - 2);
			PVector s = pts.get(i);
			// int dir=PVecMath2D.relativeCCW(p0,p1,s);
			if (PVecMath2D.relativeCCW(p0, p1, s) != PVecMath2D.CWRIGHT) {
				hull.add(s);
				i++;
			} else {
				hull.pop();
			}
		}
		return hull;
	}

	private Vector<PVector> grahamScan() {
		PVector pl = lowestPoint();
		PVector sub = new PVector(pl.x, pl.y);
		makeRelTo(sub);
		Collections.sort(pts, new Point2DComparator());
		sub.set(sub.x * -1f, sub.y * -1f, 0);
		makeRelTo(sub);
		return computeHullOfSorted(pts);
	}

	private void makeRelTo(PVector p0) {
		for (int i = 0; i < pts.size(); i++) {
			PVector p = pts.get(i);
			p.sub(p0);
		}
	}

	private PVector lowestPoint() {
		PVector minP = pts.firstElement();
		for (int i = 1; i < pts.size(); i++) {
			PVector p = pts.get(i);
			if (p.y < minP.y || (p.y == minP.y && p.x < minP.x))
				minP = p;
		}
		return minP;
	}

	class Point2DComparator implements Comparator<PVector> {
		public int compare(PVector p1, PVector p2) {
			// TODO Auto-generated method stub

			double cArea = p1.x * p2.y - p2.x * p1.y;
			if (p1.x == p2.x && p1.y == p2.y) {
				System.out.println("the same");
			}
			if (cArea < 0)
				return -1;
			if (cArea > 0)
				return 1;
			double d1 = Math.abs(p1.x) + Math.abs(p1.y);
			double d2 = Math.abs(p2.x) + Math.abs(p2.y);
			// System.out.println("sameAngle");

			if (d1 < d2)
				return -1;
			else
				return 1;
		}
	}

} // end class GrahamScan

